package 链表;
import java.util.Stack;
public class Solution5 {
    //https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9
    public static ListNode FindKthToTail1 (ListNode pHead, int k) {
        ListNode cur = pHead;
        int count = 0;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        if(count - k < 0) {
            return null;
        }
        count = count - k;
        cur = pHead;
        while (count != 0) {
            cur = cur.next;
            count--;
        }
        return cur;
    }

    //题解：
    public static ListNode FindKthToTail2 (ListNode pHead, int k) {
        //思路1：快慢指针，先让快指针移动k个单位，然后同时移动即可，始终领先k个单位
        ListNode cur = pHead;
        while (k != 0) {
            if(cur == null) {
                return null;
            }
            cur = cur.next;
            k--;
        }
        ListNode slow = pHead;
        ListNode fast = cur;
        while (fast != null) {
            fast = fast.next;
            slow= slow.next;
        }
        return slow;
    }
    public static ListNode FindKthToTail (ListNode pHead, int k) {
        //思路2：栈，往外弹k个
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = pHead;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        ListNode retHead = null;
        while (k != 0) {
            if(stack.isEmpty()) {
                return null;
            }
            retHead = stack.pop();
            k--;
        }
        return retHead;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        FindKthToTail1(node1,2);
    }
}